\documentclass[12pt,titlepage]{article}
\usepackage[spanish]{babel}
\usepackage[utf8]{inputenc}
\usepackage{amssymb}
\usepackage{graphicx} % para insertar imagenes

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% macros para pseudocodigo %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newcommand{\func}[2]{\texttt{#1}(#2)\\}
\newcommand{\tab}{\hspace*{2em}}
\newcommand{\FOR}{\textbf{for }}
\newcommand{\TO}{\textbf{ to }}
\newcommand{\IF}{\textbf{if }}
\newcommand{\INC}{\textbf{inc }}
\newcommand{\WHILE}{\textbf{while }}
\newcommand{\THEN}{\textbf{then }}
\newcommand{\ELSE}{\textbf{else }}
\newcommand{\RET}{\textbf{return }}
\newcommand{\MOD}{\textbf{ \% }}
\newcommand{\OR}{\textbf{ or }}
\newcommand{\tOde}[1]{\tab \small{O($#1$)}}
\newcommand{\Ode}[1]{\small{O($#1$)}}
\newcommand{\VSP}{\vspace*{3em}}
\newcommand{\Pa}{\vspace{5mm}}
\newcommand{\gramed}[1]{\noindent\includegraphics[scale=0.5]{#1}\\}
\newcommand{\gra}[1]{\noindent\includegraphics[scale=0.30]{#1}}
\newenvironment{pseudo}{\vspace*{2em}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newcommand{\dirmail}[1]{\normalsize{\texttt{#1}}}

\title{{\sc\normalsize Organización del computador II}\\{\bf Trabajo Práctico Nº1A}}
\author{\begin{tabular}{lcr}Thomas Fischer & 489/08 & \dirmail{tfischer@dc.uba.ar}\\Kevin Allekotte & 490/08 & \dirmail{kevinalle@gmail.com} \end{tabular}}
\date{\VSP \normalsize{Octubre 2009}}

\begin{document}

	\begin{titlepage}
		\maketitle
	\end{titlepage}

	\tableofcontents
	\newpage

	\begin{section}{Introducción}
		El objetivo de este trabajo es la implementación de algunos algoritmos de detección de bordes en imágenes. 
		Los mismos fueron programados en assembler, a muy bajo nivel, para optimizar la performance ya que son algoritmos caros en cuanto a tiempo de cómputo.
		
		La idea detrás de los algoritmos es la aplicación de un operador (una matriz) que determine el color de un pixel en función
		del diferencial de colores de los píxeles que lo rodean.
		De esta forma asignamos valores más altos a los pixels rodeados de colores con mucho diferencial, y por lo tanto en la imagen resultante quedan resaltados en blanco (sobre fondo negro) los bordes de la imagen original.
		El valor de un pixel en función de sus vecinos está determinado por la matriz operador y se calcula siempre como $$\sum_{i,j} operador[i][j] \times vecino[i][j]$$
		
		Los operadores implementados fueron 3: Operador de Sobel, operador de Prewitt y operador de Roberts.
		Al final del trabajo, medimos la diferencia de tiempo de ejecución (aproximada) que había entre nuestro algoritmo (con el operador Sobel), 
		y el algoritmo que ofrece la librería openCv, una librería muy usada en el campo de procesamiento de imágenes, que trabaja con el mismo operador.
	\end{section}

	\begin{section}{Desarrollo}
	
		\begin{subsection}{General}
			En todos los casos, el algoritmo consiste en recorrer la imagen original mediante algún método, y para cada píxel aplicar el operador correspondiente y guardar el resultado en el pixel de destino.

			La forma trivial de recorrer una matriz, sería guardar en dos variables la fila y la columna donde estamos ubicados en la misma, e ir moviendonos incrementando correspondientemente a
			las mismas. Esto nos resultaba un tanto ineficiente, ya que para referirnos a un píxel, hay que resolver la cuenta W*y + x, que implica una multiplicación, la cuál es muy cara de computar.
			Por lo tanto decidimos buscar otra forma de recorrerla.\\

			Aprovechando que la imagen en memoria se guarda como una línea de bytes, comenzando por la línea de arriba 
			y concatenándole las siguientes en orden, otra manera de recorrer los píxeles a computar es simplemente empezar con un puntero al primero que permita una aplicación de la matriz 
			(por el contorno tomado en cuenta) e ir incrementando el puntero de a byte, hasta llegar al último píxel donde se pueda aplicar la matriz.
			Avanzamos de a byte porque trabajamos con una imagen en escala de grises, que sólo necesita un byte por pixel para guardar la información.

			Además de tener una referencia a éste píxel, también se debe tener una referencia a su contorno.
			En el caso de las matrices de 3x3, se debe tener una referencia al pixel anterior, al siguiente, a los 3 de arriba y a los 3 de abajo. 
			Si \&p fuese la posición del píxel en cuestión en memoria, también necesitamos de [\&p-1], [\&p+1], [\&p-W-1], [\&p-W], [\&p-W+1], [\&p+W-1], [\&p+W] y [\&p+W+1]. 
			Para ahorrar unas cuantas sumas en cada ciclo, decidimos mantener tres punteros en vez de uno, los 3 separados entre sí por una distancia W. 
			A un nivel mas abstracto, los 3 punteros están alineados verticalmente en la matriz.
			
			Entonces (si p1, p2 y p3 son los punteros alineados y op es la matriz operador), para aplicar el operador a un pixel hay que calcular\\
			$[p1]*op[0,0]+[p1+1]*op[0,1]+[p1+2]*op[0,2]+$\\$[p2]*op[1,0]+[p2+1]*op[1,1]+[p2+2]*op[1,2]+$\\$[p3]*op[2,0]+[p3+1]*op[2,1]+[p3+2]*op[2,2]$

			Para el operador de Roberts, de 2x2, la idea es la misma pero sólo tenemos necesidad de 2 punteros, ya que solo operamos con dos filas por iteración.\\

			En todos los casos, para aplicar el operador correspondiente, simplemente llamamos a una rutina específica donde se aplican una sucesion de sumas y restas 
			y a veces left-shifts sobre los píxeles en cuestión, que serían el resultado de aplicar el operador a la sub-matriz de píxeles de la imagen. 
			De esta manera no desperdiciamos memoria en el almacenamiento de matrices, ni tiempo en computar multiplicaciones por 0 o demasiado simples como por $\pm 1$ o por $\pm 2$,
			para las cuáles existen alternativas como sumar, restar, hacer un shift o alguna combinación de las mismas, que resulta mas barato.
			
			Por ejemplo, si $op[0,0]$ es $-1$, usamos \texttt{acc-=[p1]} en vez de cargar el valor, multiplicarlo por $-1$, y sumarlo al acumulador.\\

			A continuación se detallan las particularidades de la implementación de cada operador.
		\end{subsection}

		\begin{subsection}{Operador de Sobel}
			La detección de bordes con el operador de Sobel fue implementada en tres variantes: en la dirección X, en la dirección Y y como último una suma de ambas. 
			En los tres casos la manera de recorrer la matriz es la misma y solo cambia la secuencia de operaciones (operador) aplicadas a la imagen.

			\begin{pseudo}
				\noindent \func{sobelX}{src, dst, W, H}
				\tab ${ptr}_{{src}_{1}}$ $\gets$ \&src + 1 \\
				\tab ${ptr}_{{src}_{2}}$ $\gets$ \&src + W + 1 \\
				\tab ${ptr}_{{src}_{3}}$ $\gets$ \&src + 2W + 1 \\
				\tab ${ptr}_{dst}$ $\gets$ \&dst + W + 1 \\

				\noindent \tab \WHILE ${ptr}_{{src}_{3}}+1<W*H$ \\

				\noindent \tab \tab acc $\gets$ 0 \\
				\tab \tab acc -= [${ptr}_{{src}_{1}}$-1] \\
				\tab \tab acc += [${ptr}_{{src}_{1}}$+1] \\
				\tab \tab acc -= [${ptr}_{{src}_{2}}$-1] + [${ptr}_{{src}_{2}}$-1] \\
				\tab \tab acc += [${ptr}_{{src}_{2}}$+1] + [${ptr}_{{src}_{2}}$+1] \\
				\tab \tab acc -= [${ptr}_{{src}_{3}}$-1] \\
				\tab \tab acc += [${ptr}_{{src}_{3}}$+1] \\
	
				\noindent \tab \tab [${ptr}_{dst}$] $\gets$ saturar(acc) \\

				\noindent \tab \tab \INC ${ptr}_{{src}_{1}}$ \\
				\tab \tab \INC ${ptr}_{{src}_{2}}$ \\
				\tab \tab \INC ${ptr}_{{src}_{3}}$ \\
				\tab \tab \INC ${ptr}_{dst}$ \\
			\end{pseudo}
			\begin{pseudo}
				\noindent \func{sobelY}{src, dst, W, H}
				\tab ${ptr}_{{src}_{1}}$ $\gets$ \&src + 1 \\
				\tab ${ptr}_{{src}_{2}}$ $\gets$ \&src + 2W + 1 \\
				\tab ${ptr}_{dst}$ $\gets$ \&dst + W + 1 \\

				\noindent \tab \WHILE ${ptr}_{{src}_{2}}+1<W*H$ \\

				\noindent \tab \tab acc $\gets$ 0 \\
				\tab \tab acc -= [${ptr}_{{src}_{1}}$-1] \\
				\tab \tab acc += [${ptr}_{{src}_{1}}$] + [${ptr}_{{src}_{1}}$] \\
				\tab \tab acc -= [${ptr}_{{src}_{1}}$+1] \\
				\tab \tab acc += [${ptr}_{{src}_{2}}$-1] \\
				\tab \tab acc -= [${ptr}_{{src}_{2}}$] + [${ptr}_{{src}_{2}}$] \\
				\tab \tab acc += [${ptr}_{{src}_{2}}$+1] \\

				\noindent \tab \tab [${ptr}_{dst}$] $\gets$ saturar(acc) \\

				\noindent \tab \tab \INC ${ptr}_{{src}_{1}}$ \\
				\tab \tab \INC ${ptr}_{{src}_{2}}$ \\
				\tab \tab \INC ${ptr}_{dst}$ \\
			\end{pseudo}

			El algoritmo que detecta los bordes tanto en x como en y, calcula cada diferencial por separado y luego hace la suma saturada de los dos.

			\begin{pseudo}
				\noindent \func{sobelXY}{src, dst, W, H}
				\tab ${ptr}_{{src}_{1}}$ $\gets$ \&src + 1 \\
				\tab ${ptr}_{{src}_{2}}$ $\gets$ \&src + W + 1 \\
				\tab ${ptr}_{{src}_{3}}$ $\gets$ \&src + 2W + 1 \\
				\tab ${ptr}_{dst}$ $\gets$ \&dst + W + 1 \\

				\noindent \tab \WHILE ${ptr}_{{src}_{3}}+1<W*H$ \\

				\noindent \tab \tab ${acc}_{x}$ $\gets$ 0 \\
				\tab \tab ${acc}_{x}$ -= [${ptr}_{{src}_{1}}$-1] \\
				\tab \tab ${acc}_{x}$ += [${ptr}_{{src}_{1}}$+1] \\
				\tab \tab ${acc}_{x}$ -= [${ptr}_{{src}_{2}}$-1] + [${ptr}_{{src}_{2}}$-1] \\
				\tab \tab ${acc}_{x}$ += [${ptr}_{{src}_{2}}$+1] + [${ptr}_{{src}_{2}}$+1] \\
				\tab \tab ${acc}_{x}$ -= [${ptr}_{{src}_{3}}$-1] \\
				\tab \tab ${acc}_{x}$ += [${ptr}_{{src}_{3}}$+1] \\

				\noindent \tab \tab ${acc}_{y}$ $\gets$ 0 \\
				\tab \tab ${acc}_{y}$ -= [${ptr}_{{src}_{1}}$-1] \\
				\tab \tab ${acc}_{y}$ += [${ptr}_{{src}_{1}}$] + [${ptr}_{{src}_{1}}$] \\
				\tab \tab ${acc}_{y}$ -= [${ptr}_{{src}_{1}}$+1] \\
				\tab \tab ${acc}_{y}$ += [${ptr}_{{src}_{3}}$-1] \\
				\tab \tab ${acc}_{y}$ -= [${ptr}_{{src}_{3}}$] + [${ptr}_{{src}_{3}}$] \\
				\tab \tab ${acc}_{y}$ += [${ptr}_{{src}_{3}}$+1] \\

				\noindent \tab \tab [${ptr}_{dst}$] $\gets$ saturar(${acc}_{x}$)/2 + saturar(${acc}_{y}$)/2 \\

				\noindent \tab \tab \INC ${ptr}_{{src}_{1}}$ \\
				\tab \tab \INC ${ptr}_{{src}_{2}}$ \\
				\tab \tab \INC ${ptr}_{{src}_{3}}$ \\
				\tab \tab \INC ${ptr}_{dst}$ \\
			\end{pseudo}
		\end{subsection}

		\begin{subsection}{Operador de Prewitt}

			\begin{pseudo}
				\noindent \func{prewitt}{src, dst, W, H}
				\tab ${ptr}_{{src}_{1}}$ $\gets$ \&src + 1 \\
				\tab ${ptr}_{{src}_{2}}$ $\gets$ \&src + W + 1 \\
				\tab ${ptr}_{{src}_{3}}$ $\gets$ \&src + 2W + 1 \\
				\tab ${ptr}_{dst}$ $\gets$ \&dst + W + 1 \\

				\noindent \tab \WHILE ${ptr}_{{src}_{3}}+1<W*H$ \\

				\noindent \tab \tab ${acc}_{x}$ $\gets$ 0 \\
				\tab \tab ${acc}_{x}$ -= [${ptr}_{{src}_{1}}$-1] \\
				\tab \tab ${acc}_{x}$ += [${ptr}_{{src}_{1}}$+1] \\
				\tab \tab ${acc}_{x}$ -= [${ptr}_{{src}_{2}}$-1] \\
				\tab \tab ${acc}_{x}$ += [${ptr}_{{src}_{2}}$+1] \\
				\tab \tab ${acc}_{x}$ -= [${ptr}_{{src}_{3}}$-1] \\
				\tab \tab ${acc}_{x}$ += [${ptr}_{{src}_{3}}$+1] \\

				\noindent \tab \tab ${acc}_{y}$ $\gets$ 0 \\
				\tab \tab ${acc}_{y}$ -= [${ptr}_{{src}_{1}}$-1] \\
				\tab \tab ${acc}_{y}$ += [${ptr}_{{src}_{1}}$] \\
				\tab \tab ${acc}_{y}$ -= [${ptr}_{{src}_{1}}$+1] \\
				\tab \tab ${acc}_{y}$ += [${ptr}_{{src}_{3}}$-1] \\
				\tab \tab ${acc}_{y}$ -= [${ptr}_{{src}_{3}}$] \\
				\tab \tab ${acc}_{y}$ += [${ptr}_{{src}_{3}}$+1] \\

				\noindent \tab \tab [${ptr}_{dst}$] $\gets$ saturar( saturar(${acc}_{x}$) + saturar(${acc}_{y}$) ) \\

				\noindent \tab \tab \INC ${ptr}_{{src}_{1}}$ \\
				\tab \tab \INC ${ptr}_{{src}_{2}}$ \\
				\tab \tab \INC ${ptr}_{{src}_{3}}$ \\
				\tab \tab \INC ${ptr}_{dst}$ \\
			\end{pseudo}

		\end{subsection}

		\begin{subsection}{Operador de Roberts}
	
			\begin{pseudo}
				\noindent \func{roberts}{src, dst, W, H}
				\tab ${ptr}_{{src}_{1}}$ $\gets$ \&src + 1 \\
				\tab ${ptr}_{{src}_{2}}$ $\gets$ \&src + W + 1 \\
				\tab ${ptr}_{dst}$ $\gets$ \&dst + W + 1 \\

				\noindent \tab \WHILE ${ptr}_{{src}_{2}}+1<W*H$ \\

				\noindent \tab \tab ${acc}_{x}$ $\gets$ 0 \\
				\tab \tab ${acc}_{x}$ += [${ptr}_{{src}_{1}}$] \\
				\tab \tab ${acc}_{x}$ -= [${ptr}_{{src}_{2}}$+1] \\

				\noindent \tab \tab ${acc}_{y}$ $\gets$ 0 \\
				\tab \tab ${acc}_{y}$ += [${ptr}_{{src}_{1}}$+1] \\
				\tab \tab ${acc}_{y}$ -= [${ptr}_{{src}_{2}}$] \\

				\noindent \tab \tab [${ptr}_{dst}$] $\gets$ saturar( saturar(${acc}_{x}$) + saturar(${acc}_{y}$) ) \\

				\noindent \tab \tab \INC ${ptr}_{{src}_{1}}$ \\
				\tab \tab \INC ${ptr}_{{src}_{2}}$ \\
				\tab \tab \INC ${ptr}_{dst}$ \\
			\end{pseudo}

		\end{subsection}
		
	\end{section}

	\begin{section}{Discusión}

		En cuanto a la saturación de los valores, nos planteamos que en realidad no era correcto saturar los valores negativos a 0.
		Viendo algunas imágenes nos dimos cuenta que estabamos despreciando los bordes en los cuáles aplicar el valor nos devolvía un resultado negativo, o sea, cuando el diferencial de color era negativo.
		Originalmente saturabamos estos bordes a 0 (negro), por lo que no aparecían como tales en la imagen resultante. Como la intensidad del borde en realidad debería definirse como la 'intensidad' del diferencial,
		decidimos tomar el valor absoluto del resultado luego de aplicar el operador, y saturar esto último. El resultado sobre las imágenes fue que ahora sí detectabamos todos los bordes.
		
		Sin embargo en las funciones sobelX y sobelY saturamos los valores negativos a 0, ya que la librería openCv aparenta hacerlo así y queríamos medir las diferencias de performance con las mismas condiciones.
		Para implementar la saturación, guardamos el resultado de aplicar el operador en un registro mucho mayor al del resultado (32 bit) para no perder información, 
		y luego saturamos este resultado a \texttt{0xFF} y tomamos la parte baja (8 bit) del mismo. \\
		
		
		Cuando aplicabamos los operadores en ambas direcciones, tuvimos que decidir como combinar los resultados de los mismos para darle un valor final al pixel resultante.
		Para esto surgieron un par de opciones, como sumarlos y luego saturar (idéntico a sumar las matrices y usar la matriz resultante como nuevo operador) 
		o aplicar los dos operadores por separado, saturar los resultados individuales, y luego saturar la suma de estos.
		
		Finalmente nos decidimos por la segunda opción, ya que con la primera se perdía información cuando los resultados parciales tenían signos distintos. \\


		Dado que no se pueden aplicar las matrices en los pixeles borde de la imagen, empezamos a calcular desde la segunda fila y la segunda columna hasta la anteúltima fila y anteúltima columna.
		Los pixeles de los bordes derecho e izquierdo los calculamos igual, porque no nos importa qué queda ahí, ya que no hay forma de saberlo. 
		En la práctica funciona bien porque la imagen esta guardada en una línea contínua en la memoria. Lo que sucede es que estamos tomando el último pixel de las filas anteriores en caso del borde izquierdo, 
		y el primero de las filas siguientes, en caso del derecho (lo único que afecta es que queda 'ruido' en la primera y en la última columna de la imagen).
		Supusimos que si hacíamos un chequeo de final de fila iba a bajar considerablemente la performance. \\

	\end{section}

	\begin{section}{Resultados}
		Tanto los resultados de SobelX y SobelY quedaron igual que los de la libreria openCV:\\
		\gramed{sobelxy.jpg}
		\begin{subsection}{Otras Pruebas}
			\gra{lena.jpg}
			\gra{originals.jpg}
			\begin{subsubsection}{Sobel (xy)}
				\gra{sobellena.jpg}
				\gra{sobels.jpg}
			\end{subsubsection}
			\begin{subsubsection}{Prewitt}
				\gra{prewittlena.jpg}
				\gra{prewitts.jpg}
			\end{subsubsection}
			\begin{subsubsection}{Roberts}
				\gra{robertslena.jpg}
				\gra{roberts.jpg}
			\end{subsubsection}
		\end{subsection}
		
		\begin{subsection}{Tiempos de Ejecución}
			Medimos 1000 veces el tiempo de ejecución (en ticks del clock) del algoritmo SobelX, y lo comparamos con el tiempo de ejecución del SobelX de la librería OpenCV.
			Calculamos el mínimo y el promedio para cada uno. Observamos que los resultados debenden de la computadora en la cual se ejecutan, pero aproximadamente el tiempo de ejecución de nuestro algoritmo es de 9889746 ticks de reloj y el del algoritmo de OpenCV aprox 22070207.
			
			Esto indica que nuestro algoritmo es más del doble de rápido que el de la librería. ($\frac{\texttt{tiempo de nuestro algoritmo}}{\texttt{tiempo de algoritmo de OpenCV}} = 0.45$)
		\end{subsection}
	\end{section}

	\begin{section}{Conclusiones}
		Al optimizar el recorrido de la imagen de la forma en que lo hicimos perdimos flexibilidad, pero ganamos eficiencia. La aplicación del operador esta 'hardcodeada' para mejorar la performance, pero esto significa que para modificar el operador o el tamaño de la matriz
		hay que modificar el codigo de assembler directamente. Al modularizar un poco con macros, sin embargo, la tarea se hace un poco mas agradable a la hora de encontrar el lugar a modificar o cambiar un operador.
	\end{section}

	\newpage

	\begin{section}{Manual}
		\begin{subsection}{Compilación}
			Para compilar los archivos se utiliza el Makefile. Simplemente con ejecutar el comando \texttt{make} en una consola de entorno UNIX en el directorio src, se deberia generar el binario \texttt{bordes} a partir de los archivos fuente.
		\end{subsection}
		\begin{subsection}{Ejecución}
			Para usar el ejecutable se debe ejecutar \texttt{./bordes} seguido de los siguientes parámetros en el orden en que aparecen:
			\begin{enumerate}
				\item el filtro que se desea aplicar:
				\begin{itemize}
					\item \texttt{r1} (o \texttt{roberts}): operador de Roberts
					\item \texttt{r2} (o \texttt{prewitt}): operador de Prewitt
					\item \texttt{r3} (o \texttt{sobelx}): operador de Sobel en la coordenada X
					\item \texttt{r4} (o \texttt{sobely}): operador de Sobel en la coordenada Y
					\item \texttt{r5} (o \texttt{sobel}): operador de Sobel en las coordenadas XY
					\item \texttt{webcam}: para aplicar el filtro SobelXY a la entrada de video (webcam), o a un archivo de video (si se especifica el nombre)
					\item \texttt{time}: mide los tiempos de ejecucion del algoritmo SobelX y los compara con el SobelX de OpenCV
				\end{itemize}
				\item La imagen de entrada (opcional): Si no es designada ninguna imagen de entrada, por defecto se aplicara el filtro sobre la imagen lena.bmp contenida en el mismo directorio
			\end{enumerate}
		\end{subsection}
	\end{section}

	\newpage

	\begin{section}{Archivos incluídos}
		\begin{itemize}
			\item src
			\begin{itemize}
				\item Makefile
				\item bordes.c
				\item bordes.asm
				\item macros.asm
				\item sobel.asm
				\item prewitt.asm
				\item roberts.asm
				\item otros.asm
				\item lena.bmp
			\end{itemize}
			\item exe
			\begin{itemize}
				\item bordes (bin)
			\end{itemize}
			\item enunciado
			\begin{itemize}
				\item enunciado.pdf
			\end{itemize}
			\item informe
			\begin{itemize}
				\item informe.pdf
			\end{itemize}
			\item resultados
			\begin{itemize}
				\item sobel\_x.bmp
				\item sobel\_y.bmp
				\item sobel\_xy.bmp
				\item cVsobel\_x.bmp
				\item cVsobel\_y.bmp
				\item prewitt.bmp
				\item roberts.bmp
			\end{itemize}
		\end{itemize}
	\end{section}

\end{document}
